pub fn dp_rec_mc(amount: u32) -> u32 {
    let caches = [1, 2, 5, 10, 20, 30, 50, 100];
    let mut cache = vec![0u32; (amount + 1u32) as usize];
    dp_mc(&caches, amount, &mut cache)
}


fn dp_mc(caches: &[u32], amount: u32, min_caches: &mut Vec<u32>) -> u32 {
    for a in 1..=amount {
        let mut min_cache_num = a;
        for c in caches.iter().filter(|&&x| x <= a).collect::<Vec<&u32>>() {
            let index = (a - c) as usize;
            let cache_num = 1 + min_caches[index];
            if cache_num < min_cache_num {
                min_cache_num = cache_num;
            }
        }
        min_caches[a as usize] = min_cache_num;
    }
    min_caches[amount as usize]
}
